package yartiss.engine.simulation.scheduling.policies.tools;

import java.util.SortedSet;
import java.util.TreeSet;

import yartiss.engine.simulation.system.ITask;
import yartiss.engine.simulation.system.ITaskSet;
import yartiss.engine.simulation.system.SystemMetrics;

public class DPSlacktimeManager {

	private long [] D;
	private long [] Dt;
	private long [] K;
	private long [] Fis;
	private long hyperPeriod;
	private ITaskSet ts;

	public long getSlackTime(long date, ITaskSet taskSet){
		if(this.ts != taskSet){
			this.ts = taskSet;
			hyperPeriod = SystemMetrics.hyperPeriod(taskSet);
			K = computeK(taskSet, hyperPeriod);
			D = computeD(taskSet, hyperPeriod, K);
			Dt = new long [D.length];
			showTab(K);
			showTab(D);
			//showTab(Fis);
		}
		long st = computeSlackTime(date,taskSet);
		//System.out.println("---------------------------------------------------");
		return st;
	}

	private long computeSlackTime(long absoluteDate, ITaskSet taskSet){
		long date = absoluteDate % hyperPeriod;
		int h =0;
		for (h = 0; h < K.length && K[h] < date; h++);
		//System.out.println("h="+h);
		h = h==0 ? 0 : h-1;

		long M = 0;
		for (ITask task : taskSet.getActiveTasks(absoluteDate))
			M = Math.max(M, task.getNextAbsoluteDeadline(date));
		int f;
		for(f = h+1; f < K.length && K[f] < M; f++);

		//System.out.println("h="+K[h]+"     f="+K[f]+"    M="+M);
		long sumIdles = 0;
		for (int i = D.length-1; i >= f; i--){
			//System.out.println("# "+K[i]+" : "+ D[i]);
			Dt[i] = D[i];
			sumIdles += D[i];
		}


		for (int i = f-1; i >=h+1 ; i--) {
			long Fi = Fis[i]-sumIdles;
			//System.out.println("Fis[i]="+Fis[i]+"  sumIdles="+sumIdles+" Fi="+Fi);
			for (ITask task : taskSet) {
				if(task.getNextAbsoluteDeadline(date) > K[i]){
					//System.out.println("+++"+task.getDeadline()+"   "+(task.getWcet()-task.getRemainingCost())+"    nextdi="+nextDeadline(task, date)+"   date="+date);
					Fi += (task.getWcet()-task.getRemainingCost());
				}
			}
			//System.out.println("@ "+K[i]+" : "+ Math.max(0, Fi));
			Dt[i] =  Math.max(0, Fi);
			sumIdles += Dt[i] ;
		}
		long slack = hyperPeriod-date;
		for (ITask task : taskSet) {
			long xj = task.getPeriod() - task.getDeadline();
			long t = hyperPeriod - xj - date;
			long result = t / task.getPeriod();
			if(t > 0){
				result += (t % task.getPeriod()==0 ? 0 : 1);
				slack -= result * task.getWcet();
			}
		}
		slack -= sumIdles;
		for (ITask task : taskSet) {
			if(task.getNextAbsoluteDeadline(date) > date){
				//System.out.println("+++"+task.getDeadline()+"   "+(task.getWcet()-task.getRemainingCost())+" =c-rc="+task.getWcet()+" - "+task.getRemainingCost());
				slack += (task.getWcet()-task.getRemainingCost());
			}
		}
		//System.out.println(" slack="+slack);
		int i=h+1;
		while(i< Dt.length && date+slack==K[i] ){
			slack += Dt[i];
			i++;
		}
		//System.out.println(date + " : slack="+slack);
		return slack;
	}

	private void showTab(long [] tab){
		System.out.print("[");
		for (long ki : tab) {
			System.out.print(ki+", ");
		}
		System.out.println("]");
	}

	public long [] computeD(ITaskSet taskSet,long hyperperiod, long [] kis){
		long [] delta = new long [kis.length];
		Fis = new long [kis.length];
		ITask first = taskSet.iterator().next();
		long minX = first.getPeriod() - first.getDeadline();

		for (ITask task : taskSet) 
			minX = Math.min(minX, task.getPeriod() - task.getDeadline());

		delta[delta.length-1] = minX;
		long sumDeltas = delta[delta.length-1];

		for (int i = delta.length-2; i >=0 ; i--) {
			long Fi = hyperperiod - kis[i] ;
			//System.out.println("+++++"+K[i]+"+++++++Fi="+Fi+"+++++++++++++++++");
			for (ITask task : taskSet) {
				long xj = task.getPeriod() - task.getDeadline();
				long t = hyperperiod - xj - kis[i];
				long result = t / task.getPeriod();
				if(t > 0){
					result += t % task.getPeriod()==0 ? 0 : 1;
					Fi -= result * task.getWcet();
					//System.out.println("----"+(result * task.getWcet()));
				}
				//System.out.println(Fi);
			}
			Fis[i] = Fi;
			Fi -= sumDeltas;
			delta[i] = Math.max(0, Fi);
			sumDeltas += delta[i];
		}
		return delta;
	}

	public long [] computeK(ITaskSet taskset, long hyperperiod){
		SortedSet<Long> kis = new TreeSet<Long>();
		kis.add(0L);
		for (ITask task : taskset) {
			for (long pi = 0; pi <= hyperperiod- task.getPeriod(); pi += task.getPeriod()) {
				kis.add(pi+task.getDeadline());
			}
		}
		long [] tmpK = new long [kis.size()];
		int i=0;
		tmpK[i++] = kis.first();
		for (Long ki : kis) {
			if(tmpK[i-1]!=ki)
				tmpK[i++] = ki;
		}
		return tmpK;
	}

	

}
